package com.zx._12_算法.数据结构.queue;

public class Demo3 {

    // 使用队列打印出杨辉三角的前n行，n >= 1
    // 杨辉三角
    // 杨辉三角中的每一行，都依赖于上一行，假设在队列里存储第n - 1行的数据，输出第n行时，只需要将队列里的数据依次出队列，进行计算得到下一行的数值并将计算所得放入到队列中。
    // 计算的方式：f[i][j] = f[i-1][j-1] + f[i-1][j], i 代表行数，j代表一行的第几个数，如果j= 0 或者 j = i ,则 f[i][j] = 1。
    // 但是将计算所得放入到队列中时，队列中保存的是两行数据，一部分是第n-1行，另一部分是刚刚计算出来的第n行数据，需要有办法将这两行数据分割开。
    // 分开的方式有两种，一种是使用for循环进行控制，在输出第5行时，其实只有5个数据可以输出，那么就可以使用for循环控制调用enqueue的次数，循环5次后，队列里存储的就是计算好的第6行的数据。
    // 第二种方法是每一行的数据后面多存储一个0，使用这个0来作为分界点，如果enqueue返回的是0，就说明这一行已经全部输出，此时，将这个0追加到队列的末尾。
    private static final String INTERVAL = "\t";

    public static void main(String[] args) {
        Queue queue = new Queue();
        queue.enqueue(1);
        int n = 10;
        for (int i = 1; i <= n; i++) {
            String line = "";
            int num = 0;
            for (int j = 0; j < i; j++) {
                Integer dequeue = queue.dequeue();
                line += dequeue + INTERVAL;
                // 计算下一行的数据
                int nextLine = dequeue + num;
                num = dequeue;
                queue.enqueue(nextLine);
            }
            // 每一层最后一个数字是1,上面的for循环没有计算最后一个数
            queue.enqueue(1);
            System.out.println(line);
        }
    }

}
